/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 周斌
 * Date: 2024-04-11
 * Time: 23:08
 */
public class topKFrequent {
/*    public List<String> topKFrequent(String[] words, int k) {
        // 1、统计每个单词出现的次数
        Map<String, Integer> map = new HashMap<>();
        for (String str : words) {
            if (map.get(str) == null) {
                map.put(str, 1);
            } else {
                int val = map.get(str);
                map.put(str, val + 1);
            }
        }

        // 2、遍历map 把前K个元素 放到小根堆当中
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(
                new Comparator<Map.Entry<String, Integer>>() {
                    @Override
                    public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                        if (o1.getValue().compareTo(o2.getValue()) == 0) {
                            // 存储的时候，应该找key变为大根堆存储
                            return o2.getKey().compareTo(o1.getKey());
                        }
                        return o1.getValue().compareTo(o2.getValue());
                    }
                });
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (minHeap.size() < k) {
                // 直接存到 小根堆当中
                minHeap.offer(entry);
            } else {
                Map.Entry<String, Integer> top = minHeap.peek();
                if (top.getValue().compareTo(entry.getValue()) < 0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                } else {
                    if (top.getValue().compareTo(entry.getValue()) == 0) {
                        if (top.getKey().compareTo(entry.getKey()) > 0) {
                            // 频率一样，字典序小的需要入堆
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> top = minHeap.poll();
            ret.add(top.getKey());// 默认是尾插
        }
        Collections.reverse(ret);
        return ret;
    }*/
}
